1. Technical Field
The present invention relates to a digital filter, and more particularly, to low-power CSD (Canonical Signed Digit) linear phase FIR filter architectures using vertical common subexpressions and filter design methods therefor.
2. Description of Related Art
A mobile radio communications system such as a cellular phone requires a low-power and high-speed linear phase Finite Impulse Response (FIR) filter using CMOS techniques. Currently, such low power and high speed FIR filters are designed using CSD type coefficients as filter coefficients. CSD type coefficients are expressed as binary digits subtracting 1 from 2's complement type coefficients.
Intermediate frequency (IF) processing terminals of wireless transceivers such as Digital Frequency Down Converter (DFDC) require a high-speed decimation filter. It is preferred that the high-speed/low power filter performs a multiplication using only adders (including subtracter) and delay devices. The high-speed/low power filter can perform the multiplication more efficiently with the CSD type coefficients. The CSD type coefficients are expressed using the following formula:       ∑          i      =      0              N      -      1        ⁢      a    ⁢                  ⁢    i    ⁢                  ⁢          2              -        i            
wherein the numbers a0, a1, a2, . . . , aN−1 are 2's complement type coefficients if a0=0 or −1 and ai=0 or 1 when i>0. The numbers b0, b1, b2, . . . , bN−1 are the CSD type coefficients if each bi 0, +1, −1 and no two consecutive bi are nonzero.
Technically, the CSD type coefficients are expressed by subtracting 2's complement type coefficients from “1”. For example, if the 2's complement type coefficient is “01111”, the CSD type coefficient can be expressed as “1−00001”. Hereinafter, “−1” is expressed as “n” for convenience. That is, when “−1” is expressed as “n”, the 2's complement type coefficient “01111” is expressed as a CSD type coefficient “1000n”. In such a way, all the 2's complement type coefficients are easily converted into CSD type coefficients.
Since none of the CSD type coefficients has more than (N+1)/2 nonzero bits, as compared with the 2's complement type coefficients, a filter that performs a multiplication using an adder will require a reduced number of adders in using the CSD type coefficients as filter coefficients. The multiplication for filter coefficients is performed using adders and shifts. Because the cost for the filter can be reduced by designing the shift as hard-wired logic, it is desirable to reduce the number of adders to reduce the cost for the filter.
Table 1 lists 4-bit filter coefficients expressed as 2's complement type digits and corresponding CSD type digits. As shown in Table 1, the 2's complement type coefficients have 32 digits “1” and the CSD type coefficients have 23 digits “1”. That is, the CSD type coefficients has the number of digits “1” less than in the 2′ complement type coefficients by 9 digits “1”.
TABLE 1CSD code creationNumber2's complementCSD type0.8750111100n0.75011010n00.625010101010.5010001000.3750011010n0.25001000100.12500010001000000000−0.1251111000n−0.25111000n0−0.37511010n01−0.511000n00−0.62510110n0n−0.751010n010−0.8751001n001−11000n000
Table 2 shows CSD type coefficients of a linear phase FIR filter having 11 taps.
When the total number of digits “1” or digits “n” is m, the number of (m−1) adders are needed to implement the coefficients. In Table 2, since m=17, 16 adders are needed to implement the coefficients. The number of adders can be reduced by designing a linear phase FIR filter with a common subexpression method. In Table 2, each of the coefficients h0, h1, h2, h3, h4 is symmetric to each of the coefficients h10, h9, h8, h7, h6, so that the linear phase FIR filter has two common subexpressions.
TABLE 2CSD coefficients of 11-tap linear phase FIR filter2{circumflex over ( )}−12{circumflex over ( )}−22{circumflex over ( )}−32{circumflex over ( )}−42{circumflex over ( )}−52{circumflex over ( )}−62{circumflex over ( )}−72{circumflex over ( )}−82{circumflex over ( )}−9h01h1nnh2n1h3n1h41h51h61h7n1h8n1h9nnh101
In Table 2, a digit “0” is omitted. An output signal (y) of the FIR filter is expressed by a following formula y [n]:             ∑              i        =        0                    N        -        1              ⁢                  ∑                  j          =          0                          M          -          1                    ⁢              a        ⁢                                  ⁢        i        ⁢                                  ⁢                  j          (                                                    x                ⁢                                                                  ⁢                n                            -              1                        >>            j                    ⁢                                          )                      =            ∑              i        =        0                    N        -        1              ⁢                  ∑                  j          =          0                          M          -          1                    ⁢                        a                      i            ⁢                                                  ⁢            j                          ⁢        X        ⁢                                  ⁢        i        ⁢                                  ⁢        j            
wherein since aij has digits “1, 0, or −1”, the output signal is expressed as the sum of various shifted and delayed versions of input signals (x). Each row Xij indicates “delay” of the input signal (x) and each column Xij indicates “shift” of the input signal (x). An entry ±1 in a row i and a column j is represented as ±x1 [−i]>>j, and a first row (h0) and a first column (2^−1) are defined by “x1” without i and j and determined as a reference point. Here, (2^−1) indicates −1 multiplication of 2 (i.e., 2−1=0.5) and (2^−2) indicates −2 multiplication of 2 (i.e., 2−2).
Alternatively, the linear phase FIR filter in Table 2 may be designed using a conventional horizontal common subexpression sharing method to reduce the number of adders. As shown in Table 2, the number of common subexpressions for “n0n”, “n001” and “n01” is two. Each of the horizontal common subexpressions can be implemented as follows.
x2=−x1−x1>>2: a first common subexpression
x3=−x1+x1>>3: a second common subexpression
x4=−x1+x1>>2: a third common subexpression
wherein, x2 indicates a common subexpression of “n0n”, x3 indicates a common subexpression of “n001” and x4 indicates a common subexpression of “n01”. The symbol “>>” denotes “shift” of the input signal (x) in a lowest level bit (LSB) direction. For example, if the common subexpression is “n0n” and x=1, a highest level bit (MSB) out of n0n is “−x1”, the LSB′ out of n0n is −x1 shifted to a right direction by 2 bits, so that “n0n” is expressed as the sum of the results, i.e., “−1−x1>>2”. Thus, x2 is defined as a horizontal common subexpression of “n0n”. Similar to the common subexpression for “n0n” the horizontal common subexpression for “n001” is defined as “x3”, i.e., “−x1+x1>>3”.
As shown in the formulas, 3 adders are needed to implement three common subexpressions. The output signal (y) of the filter using the horizontal common subexpression sharing method is expressed by following equation.y=x1>>8+x2[−1]>>6+x3[−2]>>3+x4[−3]>>1+x1[−4]>>1+x1[−5]+x1[−6]>>1+x4[−7]>>1+x3[−8]>>3+x2[−9]>>6+x1[−10]>>8
wherein, “x1>>8” indicates “1” in a first row (h0) and a ninth column (2^−9) in Table 2. It means that “x1=1” is 8-bit-shifted to a right direction. The numeral “1” in the first row (h0) and ninth column (2^−9) is not implemented using a horizontal common subexpression. The formula, “x2[−1]>>6” means that the first horizontal common subexpression “x2” is delayed to a vertical direction by one clock cycle (i.e., 1 tap) and shifted to a right direction by 6 bits. For example, in Table 2, if “n0n” located at a cross point of the first row (h0) and the first, second and third columns (2^−1, 2^−2, 2^−3) is expressed as “x2”, “n0n” located at a cross point of the second row and the seventh, eight and ninth columns (2^−7, 2^−8, 2^−9) is delayed and shifted “x2” (that is delayed to a vertical direction by “1” and shifted to a right direction by 6 bits).
In the above formula, since 10 additions are needed to obtain the output signal (y) and 3 additions are needed to implement 3 horizontal common subexpressions (n0n, n001, n01), 13 adders are needed to implement the filter in Table 2. The filter has a configuration of FIG. 1, when it is implemented using a Transposed Direct Form.
Referring to FIG. 1, symbol Ai (“i” is a natural number greater than 1) indicates adders connected to tap lines T1 through T6, symbol Di indicates delayers, x indicates an input signal, and y indicates an output signal. Numerals next to the tap lines indicate the number of bits to be shifted. For example, the numeral “9” next to the tap line T1 indicates that a digital input signal (x) to be filtered is shifted to a LSB direction by 9 bits. Shift registers are employed in the configuration of FIG. 1 to perform a multiplication by shifting the input signals in response to clock signals. The adders Ai having a symbol “−” at input terminals thereof perform negative additions, i.e., subtracts. It should be noted that the term “adder” used in this disclosure includes the addition function for performing positive addition as well as the subtraction for performing negative addition.
Referring again to FIG. 1, since the input signal (x) that is shifted by 9 bits is applied on the tap line T1, the coefficient h0 in Table 2 is implemented on the tap line T1. That is, “x1>>8” is implemented using a shift register. The horizontal common subexpression x2 is calculated by the shift registers, each register shifting the input signal (x) by 1 and 3, and the adder A1 connected to the line T2. The “x2[−1]>>6” is implemented by the adder A4 that adds up the output (that is shifted by 6 bits) of the shift register connected to the tap line T2 and the output of the delayer D1 (that delays the output of the tap line T1 by one clock cycle). In addition, the adder A12 implements “x2[−9]>>6”, the adder A5 implements “x3[−2]>>3”, and the adder A11 implements “x3[−8]>>3”.
The configuration of FIG. 1 multiplies the input signal (x) by 9 via the shift register, prior to performing addition operations, so that “−n” in FIG. 1 is implemented by a shift register hardware. Each of the delayers D1 through D10 delays the output of the adder inputted to the input terminal thereof by a predetermined time in order to obtain the output signal (y). The reason the coefficient h0 is implemented to −1, −4 and −7 is that since x1 is a reference point shifted by −1, x1 should be once more shifted by −1 than in the implementing formula when x1 is implemented.
An example of a common subexpression sharing method for reducing the number of adders in a Canonical Signed Digit (CSD) FIR filter is disclosed by Richard I. Hartley, “Subexpression sharing in filters using canonic signed digit multipliers”, IEEE Transaction on circuits and systems II: Analog and digital signal processing, Vol. 43, No. 10, pp. 677–688, October 1996.
Further, an example of techniques concerning a filter design architecture using a mixed integer programming (MILP) and a high-speed FIR digital filter structure using minimum numbers of adders is disclosed by M. Yagyu, A. Nishihara and N. Fujii, “Fast
FIR digital filter structures using minimal number of adders and its application to filter design”, IEICE Transaction on Fundamentals, Vol. E79 A, No. 8, pp. 1120–1129, August 1996.
The conventional methods reduce the number of adders by searching and sharing common subexpressions in coefficients but symmetric common subexpressions of linear phase filter coefficients. However, there is a problem in that the reduced number of adders is not sufficient to implement a high-speed and low-power semiconductor chip.
As described above, the conventional linear phase CSD filter employs only the horizontal common subexpressions, because it is advantage to use common subexpressions naturally generated at both sides thereof due to the symmetric structures of the filters. However, the conventional horizontal common subexpressions sharing method is not adequate to be used in high-speed and low power filters, because the method still requires relatively large numbers of adders.
Thus, a need exists to minimize the number of adders in a linear phase CSD filter, to thereby provided reduced size of semiconductor design as well as improved processing speed.